/**
 * LowerestCommonNode.java created by zhangzhidong 
 * at 上午10:29:39 2017年4月7日
 */
package exercise;

import java.util.ArrayList;

/**
 * @author zhangzhidong<br>
 * comment generated at 2017年4月7日上午10:29:39<br>
 * 
 */
public class LowerestCommonNode {
	public static void main(String args[]){
		Node n = genTree();
		ArrayList<Node> l1 = new ArrayList<>();
		ArrayList<Node> l2 = new ArrayList<>();
		fillPath(n,9,l1);
		fillPath(n,10,l2);
		System.out.println("");
		Node last = null;
		for(int i=0;i<Math.min(l1.size(), l2.size());i++){
			if(l1.get(i).value == l2.get(i).value){
				last = l1.get(i);
			}else break;
		}
		System.out.println(last);
	}
	public static boolean fillPath(Node root,int n,ArrayList<Node>l){
		if(root == null) return false;
		boolean flag = false;
		if(root.value == n){
			l.add(root);
			flag = true;
			return flag;
		}else{
			l.add(root);
			flag = fillPath(root.left,n,l);
			if(!flag)
				flag = fillPath(root.right,n,l);
			if(!flag)
				l.remove(l.size()-1);
		}
		return flag;
	}
	public static Node genTree(){
		Node head = new Node(5);
		head.left = new Node(3);
		head.right = new Node(8);
		head.left.left = new Node(2);
		head.left.right = new Node(4);
		head.left.left.left = new Node(1);
		head.right.left = new Node(7);
		head.right.left.left = new Node(6);
		head.right.right = new Node(10);
		head.right.right.left = new Node(9);
		head.right.right.right = new Node(11);
		return head;
	}
}
